package com.xiayuanxing.arithmetic.Algorithm.dynamic;

/**
 * @projectName: arithmetic
 * @className: KnapsackProblem
 * @author: xiayuanxing
 * @description: 动态规划算法解决背包问题
 * @date: 2021/10/21 16:27
 * @version: 1.0
 */
public class KnapsackProblem {


    public static void main(String[] args) {

        //物品的重量
        int[] w = {1,4,3};
        //物品的价值
        int[] val = {1500,3000,2000};
        //背包的容量
        int m = 4;
        //物品的个数
        int n = val.length;//ceshi

        //创建二维数组
        //v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值
        int[][] v = new int[n+1][m+1];
        //为了记录放入商品的情况，我们定一个二维数组
        int[][] path = new int[n+1][m+1];

        //初始化第一行和第一列
        for (int i = 0; i < v.length; i++) {
            //将第一列设置为0
            v[i][0] = 0;
        }
        for (int i = 0; i < v[0].length; i++) {
            //将第一行设置为0
            v[0][i] = 0;
        }

        //根据公式来动态规划处理
        //不处理第一行 i是从1开始的
        for (int i = 1; i < v.length; i++) {
            //不处理第一列，j是从1开始的
            for (int j = 1; j < v[0].length; j++) {
                //公式 因为程序i是从1开始的，因此原来公式中的w[i] 修改成w[i-1]
                if (w[i-1] > j){
                    v[i][j] = v[i-1][j];
                }else{
                    //因为程序i是从1开始的,所以公式调整成下面
                    //v[i][j] = Math.max(v[i-1][j],val[i-1]+v[i-1][j - w[i-1]]);
                    //为了记录商品放在背包的情况，不能直接使用上面的公式，需要用判断来划分一下
                    if (v[i-1][j] < val[i-1]+v[i-1][j - w[i-1]]){
                        v[i][j] = val[i-1]+v[i-1][j - w[i-1]];
                        //把当前情况记录到path
                        path[i][j] = 1;
                    }else{
                        v[i][j] = v[i-1][j];
                    }
                }
            }
        }

        //输出二维数组
        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print(v[i][j] + " ");
            }
            System.out.println();
        }
        //输出最后我们放入的哪些商品
       int i = path.length -1;
       int j = path[0].length - 1;
       while (i > 0 && j > 0){
           if (path[i][j] == 1){
               System.out.printf("第%d个商品放入背包\n",i);
               j -= w[i - 1];
           }
           i--;
       }

    }
}
